package leetcode.code2234;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {
	public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
		int len = flowers.length;
		long diff = 0, num = 0;
		List<Long> diffs = new ArrayList<>();
		for (int i = 0; i < len; i++) {
			if ((num = flowers[i]) < target) {
				long dif = target - num;
				diff += dif;
				diffs.add(dif);
			}
		}
		// 花够，随便种
		if (newFlowers >= diff) {
			return Math.max(1l * len * full, 1L * (len - 1) * full + 1l * (target - 1) * partial);
		}
		int notfull = diffs.size(), isfull = len - notfull;
		Long[] flower = diffs.toArray(new Long[diffs.size()]);
		Arrays.sort(flower);
		int p = 0;// 最多能多种出几个full
		long grow = newFlowers;
		while (grow >= flower[p]) {
			grow -= flower[p];
			p++;
		}
		long[] sums = this.presum(flower);
		long ans = 0, max = 0;
		for (int i = p; i >= 0; i--) {
			max = target - this.find(flower, i, notfull - 1, grow);
			long cur = 1l * (isfull + i) * full + 1L * partial * max;
			ans = Math.max(ans, cur);
			if (i > 0)
				grow += flower[i - 1];
		}
		return ans;
	}

	private long find(Long[] flower, int L, int R, long grow) {
		long ans = 0;
		long l = 0, r = flower[R];
		while (l <= r) {
			long mid = ((r - l) >> 1) + l;
			long sum = 0;
			for (int i = L; i <= R; i++) {
				if (flower[i] > mid) {
					sum += flower[i] - mid;
				}
			}
			if (sum <= grow) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	public long[] presum(Long[] nums) {
		int len = nums.length;
		long[] sums = new long[len + 1];
		for (int i = 1; i < sums.length; i++) {
			sums[i] = sums[i - 1] + nums[i - 1];
		}
		return sums;
	}

	public long sumIndex(long[] sums, int indexL, int indexR) {
		return sums[indexR + 1] - sums[indexL];
	}

	// L R范围上找最小缺口 69 / 77 个通过测试用例
	private long find1(Long[] flower, int L, int R, long grow, long max) {
		long ans = 0;
		long l = 0, r = max;
		while (l <= r) {
			long mid = ((r - l) >> 1) + l;
			long sum = 0;
			for (int i = L; i <= R; i++) {
				if (flower[i] > mid) {
					sum += flower[i] - mid;
				}
			}
			if (sum <= grow) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(7411632729l, this.maximumBeauty(H.str2array3(
				"[40742,74654,22547,18738,52156,33325,86828,63276,72224,65874,8268,91224,25184,28,69428,87064,65696,77466,90050,22475,19437,68830,56168,66104,86866,58547,66885,84417,13027,58683,76544,49343,10813,58444,16356,34161,19927,5397,16403,71540,21620,37374,49807,417,39043,38812,28248,71870,42961,40649,94016,19887,84,89541,10629,73203,14892,97132,62660,2370,5380,39769,94599,86931,83186,20501,44885,26943,77669,77891,66153,98865,32787,97342,68662,82740,78887,47815,42860,30637,60297,71183,26976,7776,2269,29377,23165,99864,53895,87432,24455,72667,52752,59991]"),
				3119579236l, 100000, 18353, 74100));
		H.compare(14, this.maximumBeauty(H.str2array3("[1,3,1,1]"), 7, 6, 12, 1));
		H.compare(30, this.maximumBeauty(H.str2array3("[2,4,5,3]"), 10, 5, 2, 6));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
